package week_eight;

public class FindTheCityWithTheSmallestNumOfNeighborsInDistance_1334 {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        //初始邻接矩阵，i到i为0
        int[][] graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = (int) 1e9;
            }
            graph[i][i] = 0;
        }

        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            int z = edge[2];
            graph[x][y] = z;
            graph[y][x] = z;
        }


        //Floyd算法
        //DP
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++) {
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }

        int ansCount = n;
        int ans = 0;

        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                // System.out.println(i+" "+j+" dist: "+graph[i][j]);
                if (i != j && graph[i][j] <= distanceThreshold) count++;
            }
            if (count <= ansCount) {
                ansCount = count;
                ans = i;
            }
        }
        return ans;
    }
}
